Intuitive notion  

Intuitively, we think of a deterministic automaton as a sequential finite state machine, which has an input tape and a reading head. The input tape holds the input word, which is read by the input head from left to right one character at a time. The automaton begins its operation in its initial state, reads the first input signal and changes its state.  This change is determined by the transition function. Then the automaton reads the next input signal and changes its state again, and so on till the end of the input word. The three step event which consists of reading the current input signal, changing the state and move the input head to the right, is called transition. This means that the operation of automaton is nothing else than a sequence of transitions. If the state to which the automaton moves from the initial state when reading the input word is a final state then we say the automata accepts or recognizes the word . 

>	restart:with(aut):AUTchar:=`  `:

 

>	showaut(genaut([a,x,b,a,y,f,b,y,a,b,x,f,f,y,a,f,x,b]),xyyxx);

 

Implementation  

We use the intuitive notion of automaton to implement it in Maple. First of all an automaton owns finitely many states. This states form a finite set, which we call the set of states. As Maple handles the set datastructure we easily define the set of state S.  

>	S:={0,1,2,3};

 

(1.2.1)

 

The input tape of automaton holds the input word, which is nothing else than a sequence of input signals. Collecting all possible signals we obtain a set, which we call alphabet. Let us denote the alphabet by . 

>

X:={x,y};

 

(1.2.2)

 

Next we implement the transition function, which we denote by . This function determines the next state to which the automaton moves from the current state in response to reading current input signal. As we see works on pairs of the form where is a state and is an input signal. The value is the next state.  

>	delta[0,x]:={0};delta[0,y]:={0,1}; delta[1,x]:={2};delta[1,y]:={2}; delta[2,x]:={3};delta[2,y]:={3};

 

 

 

 

 

 

	(1.2.3)

 

Commands  prescribe that the input signal x moves the automaton from state 1 to state 2. Note, furthermore, that we use Maple's table datastructure to implement the transition function. In the sequel we do not distinguish the transition function from its implementation.  

The last step of the implementation is to specify the initial state and the set of final states.  In the beginning of calculation the current state is the initial state (or start state), while the set of final state is used to accept or reject input words. We do not display the result of the following command as they are assignment and in these cases Maple simply echoes the values on the right hand side. 

>	Q:={0}:R:={3}:

 

We finish the implementation of automaton by collecting all defined components in a five element list...  

>	M:=[S,X,delta,Q,R];

 

(1.2.4)

 

... which is recognized by Maple as an object of type automaton. 

>	type(M,automaton);

 

(1.2.5)

 

>

 

Representations 

Unfortunately the list tells nothing about the behavior of transition function except its name. What we need is a better representation. The procedure printaut is used to display the transition table of automata.  

>	printaut(M);

 

 

 

	(1.3.1)

 

We can see the states in the first column whilst the input signals can be seen in the first row of transition table. The intersection of row labeled by the state and the column labeled by the input signal contains . It is very important to see, that our notion of automaton is nondeterministic. Indeed the next state is not uniquely determined by the current state and input signal. For example  

which means that automaton M makes a choice when being in the state 0 and reads the input signal x. The next state is either 0 or 1.  

Next command shows that automaton M is not of type deterministic. 

>	type(M,deterministic);

 

(1.3.2)

 

While the transition table can be considered as symbolic representation the transition graph serves as graphical representation. The latter is a directed graph whose vertices are labeled by the states and the edges are labeled by the input signals. The transition graph of automata can be displayed by the procedure plotaut. 

>	plotaut(M);

 

The start state is indicated by the colour green, while red coloured and bold vertices are final states. Observe that for some states there does not exist arrow beginning with this state. On the other hand there exist state for which more then one arrow is labeled by the same input signal. If for every state and every input signal there exists at most one arrow which is labeled by and whose starting point is then the automaton is deterministic. Completeness of the transition function provides at least one arrow for every state and input signal.  

Like other Maple procedures the procedures of aut package have several options, which are very effective tools to influence the behavior of the procedure in question. If we use option line, plotaut places the vertices of transition graph on a straight line instead on a circle. 

>	plotaut(M,line);

 

As we have seen, our automaton is nondeterministic. If we need the deterministic automaton associated with M, we use procedure ConDet (Construct Deterministic automaton). For the moment it doesn't matter what the word "associated" means. Just realize that ConDet establishes a new automaton which is not only of type deterministic but as well as of type complete, which means that the transitions are defined for all states and input signals. 

>	N:=ConDet(M);

 

(1.3.3)

 

>	plotaut(N);

 

>	type(N,deterministic);

 

(1.3.4)

 

>	type(N,complete);

 

(1.3.5)

 

This transition graph is not very nice, and what's wrong it is messy.  The picture becomes nicer if we rename the vertices using the procedure renaut, with which we can rename the states and also the input signals of existing automata. The option state=A prescribes that the new name of first state will be A, the second will be B, and so on. We also can use numbers as a name of vertices. 

>	renaut(N,sta=A);               # Point of practice (PoP)

 

(1.3.6)

 

>	plotaut(%);                    # EoP

 

Seeing this picture we can not realize the wonderful symmetry of transition graph. These details appears if we use the option of plotaut with which we can determine the coordinates of different vertices. 

>	par:={0}=[-1,-1],{0,1}=[0,-1],{0,1,2}=[1,-1],{0,1,2,3}=[2,-1]: par:=par,{0,3}=[-1,.5],{0,2}=[0,0],{0,2,3}=[2,.5],{0,1,3}=[1,0]:

 

The equality {0}=[-1,-1] prescribes that the vertex of name {0} should be placed to the coordinate [-1,-1] and similarly for all other states. 

>	plotaut(N,par);

 

Operation 

The tool with which we can describe the operation of automaton is the generalized transition function Delta., which works on input words instead of input signals. While the transition function delta specifies the next state where the automaton moves to after reading an input signal, Delta tells us the state to which the automaton moves after reading an arbitrary input word. The first parameter of Delta is an automaton, the second is a state (or a set of states) of this automaton, while the third parameter is an input word. Let see how Delta works.  

>	plotaut(M,line);

 

>	w:=yxyxy;                      # Point of practice (PoP)

 

(1.4.1)

 

>	Delta(M,0,w);                  # EoP

 

(1.4.2)

 

As we see the result of computation is which can be interpreted that the nondeterministic automaton M moves from the start state either to the state 0 or to the state 3 after reading the input word w. 

On the some time nothing is known about what happened during this operation. The some number of transitions must have been executed, in fact as many signal occurs in input the word. From didactic point of view we say that at this stage Delta works as a black box. We are aware of its input and and see its output. Owing to interactive interface of Maple we are able to repeat the calculation while alter the input word as many times as we want. We experiment and try to find out what happens behind the scenes. 

Using its option Delta becomes much more communicative, i.e. it becomes a white box. The option tr1 (trace level 1) forces Delta to display the sequence of sets of possible states (SoPS).  

>	Delta(M,0,w,tr1,show);        # EoP

 

 

-Delta begins with {0}

 

 

 

-Delta({0},y) = {0, 1} -Delta({0, 1},x) = {0, 2} -Delta({0, 2},y) = {0, 1, 3} -Delta({0, 1, 3},x) = {0, 2} -Delta({0, 2},y) = {0, 1, 3}
Result of Delta:
	(1.4.3)

 

As a consequence of nondeterminism we can not uniquely determine the current state of automaton. Instead in each step of calculation we are able determine a subset of the set of states, namely the subset of all states which could be the current state of automaton which is called the Set of Possible States (SoPS). The first SoPS consists of the initial state(s). Reading the input signal x automaton M has only one choice, so the next SoPS is also {0}. The second signal of the input word is y. Now the automaton has two choices, it may choose either the state 0 or the state 1. So the third SoPS is etc. 

The option tr2 (trace level 2) display more details of computation.  

>	Delta(M,0,w,tr2,show);

 

 

-Delta begins with {0}

 

 

 

.0,y->{0, 1} -Delta({0},y) = {0, 1} .0,x->{0} .1,x->{2} -Delta({0, 1},x) = {0, 2} .0,y->{0, 1} .2,y->{3} -Delta({0, 2},y) = {0, 1, 3} .0,x->{0} .1,x->{2} -Delta({0, 1, 3},x) = {0, 2} .0,y->{0, 1} .2,y->{3} -Delta({0, 2},y) = {0, 1, 3}
Result of Delta:
	(1.4.4)

 

The list of states touched during processing the input word w is called the run corresponding the input word w. For example the list is a possible run of automaton M, associated with the input word . If we use the option runs procedure Delta returns the set of possible runs corresponding to the input word given as its third argument. The set of possible runs can be visualized by procedure plotaut with the input word as second parameter. 

>	Delta(M,0,w,runs);

 

(1.4.5)

 

>	plotaut(M,w);

 

In case if the last SoPS corresponding the input word w owns a final state , we say the automaton recognizes or accept the word w. Otherwise the automaton rejects the input word. The set of all acceptable word  by automaton M is called the language accepted by M and is called by . 

Acceptance is implemented by the procedure accept, which is a Boolean function. 

>	accept(M,w);

 

(1.4.6)

 

As before we again miss something. Some more detail about the intermediate operation. Using the option show, procedure accept displays at last SoPS, the set of final states, and a logical value. 

>	accept(M,w,show);

 

 

 

 

 

Result of Delta:
Result of accept:
	(1.4.7)

 

The most impressive aid to understand the operation of an automaton the animation of its operation. This can be reached by using the option animation. 

>	accept(M,w,animation):

 

>

 

Worked exercise 1 

Let w is a word over the alphabet . This string can be considered as a binary representation of a natural number. Denote this number by and let 

. 

Construct automaton M which recognizes this language. 

Hint 

. 

How do these equality change if we calculate modulo 3? 

Solution 

Let the states of automaton be the complete residue system modulo 3. Let be the alphabet of automaton. For all state and let us define 

. 

Some example for transitions:  

Now we can generate the automaton and display the transition graph. Plotaut gives nicer picture when using option line. 

>	M:=genaut([0,0,0,0,1,1,1,0,2,1,1,0,2,0,1,2,1,2],0,0);

 

(2.1.1)

 

>	printaut(M);

 

 

 

	(2.1.2)

 

>	plotaut(M);

 

>	plotaut(M,line);

 

Check some input words for recognition. 

>	w:=`10010`:                     # PoP

 

>	accept(M,w,tr1,sho);            # EoP

 

 

 

 

 

 

 

-Delta begins with 0 -Delta(0,`1`) = 1 -Delta(1,`0`) = 2 -Delta(2,`0`) = 1 -Delta(1,`1`) = 0 -Delta(0,`0`) = 0
Result of Delta:
Result of accept:
	(2.1.3)

 

Display the words of length 0..5 belonging to L(M).  

>	langaut(M,0..5,group,show);

 

 

 

 

 

 

 

 

 

 

 

 

 

 

length 0:
length 1:
length 2:
length 3:
length 4:
length 5:
Result of langaut:
	(2.1.4)

 

The result is much more comprehensible if we convert the binary string to decimal numbers. 

>	map(x->convert(x,decimal,2),%);

 

(2.1.5)

 

The result is self explanatory.  

On the same time notice, that leading zeros are present in binary strings (see worked exercise 2).  

Worked exercise 2 

Alter the automaton M constructed in the former exercise so that it does not recognize binary strings with leading zeros. 

Solution 

Display the transition table of M. 

>	printaut(M);

 

 

 

	(2.2.1)

 

We have to introduce a new initial state for which the input signal 1 is defined only. Denote the new start state by s and add it to the automaton. 

>	N:=addaut(M,ini=s);

 

(2.2.2)

 

Now we have two initial states. The old one has to be erased. 

>	N:=delaut(N,ini=0);

 

(2.2.3)

 

>	printaut(N);

 

 

 

	(2.2.4)

 

For the moment there is no transition defined for the new initial state. The question is to which state have to move the automaton from state s when reading the input signal 1? The answer is that the result of new transition has to be the same as in the original case, i.e.  

. 

>	N:=addaut(N,tra=[s,1,1]);plotaut(N);

 

Check the result... 

>	langaut(N,0..5,group);

 

 

 

 

 

 

 

 

 

 

 

 

 

length 0:
length 1:
length 2:
length 3:
length 4:
length 5:
	(2.2.5)

 

>	map(x->convert(x,decimal,2),%);

 

(2.2.6)

 

Almost correct. Unfortunately we lost the string `0`. In order to accept it we add a new final state to which the automaton moves when reading `0`. 

>	N:=addaut(N,tra=[s,0,f],fin=f); plotaut(%);

 

>	map(x->convert(x,decimal,2),langaut(N,0..6));

 

(2.2.7)

 

Worked exercise 3 

Construct automaton which recognizes a word w over the alphabet if and only if the first signal of w is 1 and w ends by two zeros. Check the type of automaton. Determine and visualize the possible set of runs associated with different input words.  

Solution 

Following György Pólya let us begin by solving a simpler problem. Construct automaton which recognizes the one element set . The solution is evident. 

>	M:=genaut([a,1,b],a,b);plotaut(%);

 

How should we alter this automaton to recognize words of the form 1q, where q is arbitrary word over the alphabet This requirement prescribes that the automaton should be able to continue the calculation after the first 1, whatever is the suffix of the input word. This can be reached by adding two new transitions, namely two loops. Both of the input signal should leave the state b unchanged. 

>	M:=addaut(M,transition={[b,0,b],[b,1,b]});plotaut(%);

 

In the and we have to alter the automaton so that it ends its operation with two zeros. This requires two new states. From state b the input signal 0 should move M to a new state, and a second 0 from this state to another state. 

>	M:=addaut(M,transition={[b,0,c],[c,0,d]});plotaut(%);

 

The transitions seem to be correct. The recognition can begin with 1, continue with arbitrary word in the state b, and end by two zeros. But from now on the state b is not a correct final state, the correct recognition is made by the state d. So we have to erase b from the set of final state and add state d to it. 

>	M:=addaut(delaut(M,final=b),final=d); plotaut(%);

 

The option line may result in more nicer picture. 

>	plotaut(M,line);

 

The datastructure of M can be checked by the type procedure. We see that automaton M is neither deterministic nor complete. 

>	type(M,automaton);

 

(2.3.1)

 

>	type(M,deterministic);

 

(2.3.2)

 

>	type(M,complete);

 

(2.3.3)

 

The sequence of SoPS (set of of possible state) and the set of possible runs can be produced by using Delta. 

>	w:=`1100`;

 

(2.3.4)

 

>	Delta(M,{a},w,tr1):

 

 

-Delta begins with {a} -Delta({a},`1`) = {b} -Delta({b},`1`) = {b} -Delta({b},`0`) = {b, c} -Delta({b, c},`0`) = {b, c, d}
	(2.3.5)

 

>	Delta(M,{a},w,runs);

 

(2.3.6)

 

>	plotaut(M,w);

 

Worked exercise 4 

Create deterministic and complete automaton which recognizes the language { | }. 

As before begin with a much simpler problem. Erase the letter y at the end of words to be accepted and consider first the language  

{ | }.  

This language consists of words like  , xxx, xxxxxx, xxxxxxxxx, ...etc, which can be easily recognized by a three state automaton. 

>	M:=genaut([a,x,b,b,x,c,c,x,a],a,a);

 

(2.4.1)

 

>	plotaut(M);

 

Now we alter this automaton so that it recognize words  y, xxxy, xxxxxxy, xxxxxxxxxy, ...etc. We have nothing else to do than to create a new transition for state a and the input signal y. The result of this transition must be the new final state, which on the same time can be none of the existing states (why?). So we have to establish a new state, say f. As the state a is no more final state, we first delete it from set of final states and then add a new transition and a new final state. 

>	N:=addaut(delaut(M,fin=a),tra=[a,y,f],final=f);

 

(2.4.2)

 

>	type(N,deterministic);

 

(2.4.3)

 

>	plotaut(N);

 

This automaton is the solution of our exercise. Let us consider the characteristic features of this automaton. It is deterministic, but not complete. Indeed, several transitions are not defined. These transitions, however, are irrelevant from the point of view of word recognition. The equivalent complete automaton can be created by procedure ConCom (CONstruct Complete automaton). 

>	U:=ConCom(N);

 

(2.4.4)

 

>	plotaut(U);

 

Worked exercise 5 

Create deterministic automaton which recognizes a word over the alphabet {0,1} if and only if it contains three consecutive 1s . 

Similar to the solution of previous exercise we divide the problem into simpler subproblems. The recognition of three consecutive 1s is an easy task. 

>	M:=genaut([a,1,b,b,1,c,c,1,d],a,d);

 

(2.5.1)

 

>	plotaut(M,line);

 

The words we have to recognize contains a subword 111, and besides it can have an arbitrary suffix ... 

>	M:=addaut(M,transition={[d,0,d],[d,1,d]});

 

(2.5.2)

 

>	plotaut(M,line);

 

... and an arbitrary prefix. 

>	M:=addaut(M,transition={[a,0,a],[a,1,a]});

 

(2.5.3)

 

>	plotaut(M,line);

 

>	type(M,deterministic);

 

(2.5.4)

 

This automaton is neither complete nor deterministic. If we insisted on obtaining a deterministic automaton we use procedure ConDet (CONstrunct DETereministic automaton). As the stets of resulted deterministic automaton are states  fro the sake of simplicity it worth to rename them. 

>	ConDet(M);

 

(2.5.5)

 

>	N:=renaut(%,sta=A);

 

(2.5.6)

 

>	plotaut(N);

 

To produce the minimal state automaton recognizes the same language we use the procedure ConMin (CONstrunct MINimal automaton). 

>	plotaut(renaut(ConMin(N),sta=A));

 

>

 

More exercises 

Construct automata recognizing the following languages: 

a)  

b)  

c)  

d)  

e)  

f)  

g)  

h) Describe L(M) for the following automaton: 

>	M:=genaut([1,a,2,1,b,3,2,a,3,2,b,1,3,a,1,3,b,2],1,{1});

 

(2.6.1)

 

Union construction 

We are looking for an automaton which recognizes a word w over the alphabet if and only if w does not contain two different signal and a length of all words is congruent 0 modulo 3. This language equals to the union of two very simple languages: 

. 

It is easy to construct automata recognizing these languages. 

>	M:=genaut([a,x,b,b,x,c,c,x,a],a,a): printaut(M);

 

 

 

	(3.1.1)

 

>	N:=genaut([A,y,B,B,y,C,C,y,A],A,A):printaut(N);

 

 

 

	(3.1.2)

 

As the union construction insists on automata with the same alphabet, we have to supplement the alphabet of both automaton. 

>	M:=addaut(M,inp=y):printaut(M);

 

 

 

	(3.1.3)

 

>	N:=addaut(N,inp=x):printaut(N);

 

 

 

	(3.1.4)

 

The union construction can be performed by procedure Construct, whose first parameter is the name of construction, while the second the list of automata on which the construction is to be performed. 

>	P:=Construct(`union`,[M,N]);

 

(3.1.5)

 

Display the transition graphs of these three automata to see what have we done. 

> plotaut(M);     >

> plotaut(N);     >

> plotaut(P,   sort=[a,b,c,C,B,A]);     >

The transition graph of P is the union of the transition graphs of M and N. Construct simply joined the graphs of two automata by simply putting them next to each other. Automaton P recognizes the union of L(M) and L(N), indeed. If it gets an input word, it makes a choice. It decides with which initial state it begins to work, and works according to that automaton whose start state it has been chosen. 

Product construction 

Let us start with generating two automata M and N, and construct a third one which recognizes the intersection of the languages L(M) and L(N).  

>	M:=genaut([a,x,b,b,x,c,c,x,a,a,y,a,b,y,b,c,y,c],a,a):plotaut(%);

 

This automaton is very similar to that  we introduced in the previous section. It can be seen that this three state automaton recognizes a word w over the alphabet if and only if the number of occurrences of x in w can be divided by 3. Let the next automaton be one which recognizes words having even number of y.  

>	N:=genaut([A,y,B,B,y,A,A,x,A,B,x,B],A,A):plotaut(%);

 

Again we use the procedure Construct, but now the name of construction is product instead of union. 

>	P:=Construct(product,[M,N]);

 

(3.2.1)

 

What kind of automaton we have obtained? One thing is clear: the states of new automaton in ordered pairs. The first component of all pairs is a state of automaton M, while the second comes from N. The initial state is created from the initial states of M and N, and the same is true for final state. A closer look at the transition tables clarify the operation of new automaton. 

> printaut(M);       (3.2.2)   >

> printaut(N);       (3.2.3)   >

> printaut(P);       (3.2.4)   >

Observe that the automaton P synchronizes the operation of automata M and N in such a way that P works on the first component of is states according to the transition function of M and on the second component of the states works according to automaton N, i.e. 

holds for every state s and input signal ξ. Consider the transition graph of P. 

>	plotaut(P);

 

Although we feel that there must be some symmetry in this graph, it not really nice. We can, however produce another graph which clearly shows the beautiful inner structure of automaton P.  

>	par:=[a,A]=[-1,0],[b,A]=[0,0.5],[c,A]=[1,0]: par:=par,[a,B]=[-1,1],[b,B]=[0,1.5],[c,B]=[1,1]: plotaut(P,par);

 

Instead of trying to prove the equality 

we may ask how has automaton P constructed? Call procedure Construct by using the options state and show.  

>	Construct(product,[M,N],state,show);

 

 

 

 

 

 

 

 

 

Result of Compose:
	(3.2.5)

 

We see that Construct performed steps namely six steps. In each step it created an SoGS which stands for Set of Generated States.  These generated set form an  increase sequence. The last SoGS is the set of state of the generated automaton. At this stage it's enough, further details are coming later. 

Subset construction 

As usual we begin with generating a nondeteministic automaton and immediately plot its transition graph.  

>	M:=genaut([a,{x,y},a,a,x,b,b,x,c,c,y,f]);

 

(3.3.1)

 

>	plotaut(M,line);

 

Subset construction aims to construct equivalent deterministic automaton, i.e. a deterministic automaton P which recognizes the same language. Again we use Construct but now the name of construction is set. The second parameter is a one element list. 

>	P:=Construct(set,[M]);

 

(3.3.2)

 

First of all we check, if the result is dereteministic. 

>	type(P,deterministic);

 

(3.3.3)

 

Now let's take a look on the states of new automaton. Remember that in case of product construction Construct established ordered pairs. Now we have got sets.More precisely all these sets are subset of the set of states of the original automaton. What about the transition function of P? 

> printaut(M);       (3.3.4)   >

> printaut(P);       (3.3.5)   >

It is easy to check, that  

for all state A and input signal ξ. Ask Construct to tell something about its operation. As before use options show, and state. 

>	Construct(set,[M],show,state);

 

 

 

 

 

 

 

Result of Compose:
	(3.3.6)

 

In this case Construct also generated an increasing sequence of sets and the last generable set became the set of states of new automaton. Now we are eager to now more about what happens behind the scenes. We ask further details by using option trace2. 

>	Construct(set,[M],show,state,trace2);

 

 

 

 

 

 

 

 

 

 

 

[{a}]->pop({a})->[] .delta({a},x) = {{a, b}} ..push({a, b}): [{a, b}] .delta({a},y) = {{a}}
[{a, b}]->pop({a, b})->[] .delta({a, b},x) = {{a, b, c}} ..push({a, b, c}): [{a, b, c}] .delta({a, b},y) = {{a}}
[{a, b, c}]->pop({a, b, c})->[] .delta({a, b, c},x) = {{a, b, c}} .delta({a, b, c},y) = {{a, f}} ..push({a, f}): [{a, f}]
[{a, f}]->pop({a, f})->[] .delta({a, f},x) = {{a, b}} .delta({a, f},y) = {{a}}
Result of Compose:
	(3.3.7)

 

We have got the answer we wanted. We see 'push' and 'pop' which tells us evidently that Construct uses a stack. At the very beginning SoGS consists of the one element and the stack contains. Next it takes the element s from the top of stack (pop it), and calculate and if this set in not belongs to SoGS then it is supplemented to it. The same is done for the input signal y, i.e. if then . This ends step 1, and all this is repeated until the stack is not empty. The last SoGS is the set of states of generated automaton. 

Summary 

The main concept behind the procedure Construct can be summarized as follows.  

1. Imagine a set , a universe from which we will choose the states of new automaton. 

2. Choose one element of universe, this will be the initial state of new automaton. 

3. Specify how the new transition function works on the elements of universe. 

4. Perform the algorithm described earlier, i.e. beginning with the initial state calculate the sequence of SoGSs. The last SoGS serves as the set of state of new automaton. 

5. Specify the final state(s) of new automaton. 

6. Put all these element to a list and build the new automaton. 

The Construct procedure 

We demonstrate these process with the product construction. First of all we need two automaton. 

>	M:=genaut([a,x,b,b,{x,y},b,a,y,c,c,{x,y},c],a,{b});plotaut(%);

 

>	N:=genaut([1,y,2,2,y,3,3,{x,y},3,1,x,4,2,x,4,4,{x,y},4],1,{3});plotaut(%);

 

Now we do not care of what languages are accepted by these automata. We focus on construction instead. The first step of implementation is to declare that the set input signal of new automaton is the same as that of M. Recall the second component of an automaton type object is nothing else that the alphabet. 

>	newinp:=M[2];

 

(3.4.1)

 

Next we specify the initial state of new automaton. Our universe is the Cartesian product of the set of states of two automaton. The ordered pair consisting  of the initial states of two automata is declared as the initial state of new automaton. 

>	newini:=Cartesian(M[4],N[4]);

 

(3.4.2)

 

The most important step is to specify the rules, which determines the operation of new automaton. This is implemented by the procedure newtra. This procedure supposes to get a list of automata, a state and an input signal. 

>	newtra:=(l,a,x)->{[Delta(l[1],a[1],x),Delta(l[2],a[2],x)]};

 

(3.4.3)

 

In the end the final states are stored in the variable newfin. 

>	newfin:=Cartesian(M[1],N[5]) union Cartesian(M[5],N[1]);

 

(3.4.4)

 

The last step of the implementation is to call procedure Compose which is the "construction engine" of aut package. Actually it is Compose which performs the algorithm we described before. 

>	Compose(generate,[M,N],[newinp,newtra,newini,newfin]);

 

(3.4.5)

 

>	plotaut(%,sort=[[c,3],[b,4]]);

 

To demonstrate the power if Compose we give two further useful application. Consider a new automaton M . 

>	M:=genaut([a,x,b,b,x,{c,a},e,x,c,e,y,b,g,x,{e,b},g,y,f],a,{f,c});

 

(3.4.6)

 

>	plotaut(M,a=[-1,0],b=[0,0],c=[1,0],g=[-1,1],e=[0,1],f=[-2,1],plotpar=[scaling=constrained]);

 

It is easy to see that states a redundant states. Neither of them can take part in word recognition. To show another useful application of Compose we construct the initially connected subautomaton of M, i.e. we get rid of the unnecessary states. 

>	newinp:=M[2]; newini:=M[4]; newtra:=(l,a,x)->Delta(l[1],a,x); newfin:=M[5];

 

 

 

 

	(3.4.7)

 

>	N:=Compose(generate,[M],[M[2],newtra,newini,newfin]);

 

(3.4.8)

 

>	plotaut(N,[1,0],line);

 

Although N has got two input signals x and y it haven't got any y-transition. So N is not of type complete. Construct a new automaton N from M by adding a new state τ to the set of states of M. Next keep all defined transition of M unchanged in N and specify every undefined transition of M as τ in N.  

>	newtra:=proc(l,a,x) if a=tau then {tau} elif Delta(l[1],a,x,set)={} then  {tau} else  Delta(l[1],a,x,set) fi end;

 

(3.4.9)

 

>	newinp:=N[2]; newini:=N[4]; newfin:=N[5];

 

 

 

	(3.4.10)

 

>	N:=Compose(generate,[N],[newinp,newtra,newini,newfin]);

 

(3.4.11)

 

>	printaut(N);

 

 

 

	(3.4.12)

 

>	plotaut(N,tau=[1,1],c=[2,0],line);

 

>

 

Worked exercise 1 

Consider the following two deterministic automata.  

Use the product construction and create automata accepting  a) the intersection and b) the union of languages accepted by these automata. 

Solution 

The first step is to establish the automata. 

>	M:=renaut(genaut([[1,2],[2,1]],1,2),inp=x);plotaut(%);

 

>	N:=renaut(genaut([[2,3,1],[3,1,2]],1,3),inp=x);plotaut(%);

 

Next call Construct with the first parameter product. Notice, it is enough to give the first three character of the construction name. 

>	P:=Construct(pro,[M,N]);

 

(4.1.1)

 

Finally supplement the set of final states with all pairs [r,s] of which r is a final state of M or s is a final state of N. 

>	Q:=addaut(P,fin={[2,1],[2,2],[1,3],[2,3]});

 

(4.1.2)

 

Worked exercise 2 

Convert the following automaton to an equivalent deterministic one using the subset construction. 

>	M:=genaut([1,{x,y},1,1,x,2,2,x,3,3,x,4],1,4);plotaut(%,line);

 

>	Q:=Construct(set,[M]);printaut(%);

 

 

 

 

	(4.2.1)

 

>	Q:=renaut(Q,sta=A,cod);printaut(%);

 

 

 

 

 

 

	(4.2.2)

 

>	plotaut(Q);

 

Worked exercise 3 

More exercise 

1. Construct automata which accepts the intersection (union) of the languages accepting by the following pairs of automata. 

   a) 

>	M:=renaut(genaut([[2,1],[2,1]],1,2),inp=x);

 

(4.4.1)

 

>	N:=renaut(genaut([[1,2],[2,1]],1,2),inp=x);

 

(4.4.2)

 

>

 

   b) 

>	M:=renaut(genaut([[2,3,1],[3,1,2]],1,{2,3}),inp=x);

 

(4.4.3)

 

>	N:=renaut(genaut([[3,1,2],[2,3,1]],1,{3}),inp=x);

 

(4.4.4)

 

>

 

2. For the following automata 

• Display the transition table and the transition graph

• Find words which are accepted

• Find words which are not accepted

• Show animation how the automaton accepts the word

• Convert the automata to equivalent deterministic one.

a) 

>	M:=genaut([1,a,{1,2,3,4},1,b,2,2,b,3,3,b,4],1,1);

 

(4.4.5)

 

b) 

>	M:=genaut([1,x,{1,2},2,y,{1,2}],1,1);

 

(4.4.6)

 

c) 

>	M:=genaut([1,x,{1,2},1,y,1,2,x,3,3,y,4],1,4);

 

(4.4.7)

 

d) 

>	M:=genaut([1,x,{1,2},1,y,1,2,x,3,3,y,4,4,{x,y},4],1,4);

 

(4.4.8)

 

>